/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package ia_psr.algoritmos;

/**
 *
 * @author Rubén Avalos Elvira y Fabiana Celiberti Tapie
 */
import ia_psr.problemas.IConjunto;
import ia_psr.problemas.IProblema;
import ia_psr.problemas.Variable;
import ia_psr.graph.Arista;
import ia_psr.graph.Nodo;
import ia_psr.graph.GrafoRestricciones;
import ia_psr.graph.NodoPSR;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
public class PSRMinimoValorRestante extends PSRBacktracking {
    // tabla de propagacion de restricciones
    protected final ArrayList< LinkedList<Variable> > tabla; // tabla comprobacion hacia delante;
    
    public PSRMinimoValorRestante() {
        super();
        tabla = new ArrayList< LinkedList<Variable> >();
    }
    
    public GrafoRestricciones resolver(GrafoRestricciones g, IConjunto c) {
        boolean resultado;
        this.g = (GrafoRestricciones)g;
        this.variables = c;
        solucion = false;
        nodosExpandidos = 0;
        variablesExpandidas = 0;
        tabla.clear();
        initGrafo();
        initTabla();

        executionTime = System.nanoTime();
        resultado = iResolver(variables.elementos.get(0));
        executionTime = (System.nanoTime() - executionTime);

        if (!resultado) {
            System.out.println("No se ha encontrado solucion");
        }

        return this.g;
    }

    protected void initTabla() {
        for (Nodo nodo : g.getNodos()) {
            LinkedList<Variable> l = new LinkedList<Variable>();
            for (Variable v : variables.elementos) {
                l.add(v);
            }
            tabla.add(l);
        }
    }

    // Elegimos el nodo con el menor numero de valores asignables (MVR)
    public NodoPSR nextNode() {
        int CurrentMVRIndex = -1;
        int CurrentMVR = Integer.MAX_VALUE;
        for(Nodo nodo : g.getNodos()) {
            NodoPSR n = (NodoPSR)nodo;
            if (n.valor.getValue() == null) {
                int nodoIndex = g.getNodos().indexOf(n);
                LinkedList<Variable> dominioXi = tabla.get(nodoIndex);
                if (dominioXi.size() < CurrentMVR) {
                    CurrentMVR = dominioXi.size();
                    CurrentMVRIndex = nodoIndex;
                }
            }
        }
        return (CurrentMVRIndex != -1) ? (NodoPSR)g.getNodos().get(CurrentMVRIndex) : null;
    }

    public synchronized boolean iResolver(Variable v) {
        return iiResolver(v, tabla);
    }

    protected boolean iiResolver(Variable v, ArrayList< LinkedList<Variable> > t) {
        if (solucion)
            return true;
        int resultadoComprobacion = g.estadoValido();
        if (resultadoComprobacion == IProblema.VALIDO) {
            solucion = true;
            return true;
        }
        if (resultadoComprobacion == IProblema.NO_VALIDO)
            return false;

        Collections.copy(tabla, t); // nextNode usa tabla
        NodoPSR n = nextNode();// Aplicacion de la heuristica 1
        ++nodosExpandidos;

        boolean resultado;

        int nodeIndex = g.getNodos().indexOf(n);
        LinkedList<Variable> listaVariables = t.get(nodeIndex);
        ArrayList< LinkedList<Variable> > taux;
        taux = cloneTable(t);
        for (Variable var : listaVariables) {
            ++variablesExpandidas;
            g.asignVariable(n, var);
            taux = propagarRestriccion(n, var, taux);
            resultado = iiResolver(var, taux);
            if (resultado)
                return true;
            else {
                g.resetNodo(n);
                // restablecer la restriccion (volver a añadir la variable a la tabla en los nodos adjacentes
                taux = restablecerRestriccion(n, var, taux);
            }
        }
        return false;
    }

    protected ArrayList< LinkedList<Variable> > propagarRestriccion(NodoPSR n, Variable v, ArrayList< LinkedList<Variable> > t) {
        for (Arista a : n.getAristas()) {
            Nodo nDestino = a.destino;
            int nodeIndex = g.getNodos().indexOf(nDestino);
            LinkedList<Variable> variablesDestino = t.get(nodeIndex);
            variablesDestino.remove(v);
        }
        return t;
    }

    protected ArrayList< LinkedList<Variable> > restablecerRestriccion(NodoPSR n, Variable v, ArrayList< LinkedList<Variable> > t) {
        for (Arista a : n.getAristas()) {
            Nodo nDestino = a.destino;
            int nodeIndex = g.getNodos().indexOf(nDestino);
            LinkedList<Variable> variablesDestino = t.get(nodeIndex);
            variablesDestino.add(v);
        }

        return t;
    }

    protected ArrayList< LinkedList<Variable> > cloneTable(ArrayList<LinkedList<Variable>> t) {
        ArrayList<LinkedList<Variable>> taux = new ArrayList<LinkedList<Variable>>();
        for (LinkedList<Variable> l : t) {
            LinkedList<Variable> laux = new LinkedList<Variable>();
            for (Variable v : l) {
                laux.add(v);
            }
            taux.add(laux);
        }
        return taux;
    }

}
